// https://www.lintcode.com/problem/meeting-rooms-ii/

// /**
//  * Definition of Interval:
//  * classs Interval {
//  *     int start, end;
//  *     Interval(int start, int end) {
//  *         this->start = start;
//  *         this->end = end;
//  *     }
//  * }
//  */

// class Solution {
// public:
//     /**
//      * @param intervals: an array of meeting time intervals
//      * @return: the minimum number of conference rooms required
//      */
     
//     void sort_interval(vector<Interval> &intervals)
//     {
//         for (int i = intervals.size() - 1; i >= 0; --i)
//         {
//             for (int j = i; j >= 0; --j)
//             {
//                 if (intervals[i].start < intervals[j].start)
//                 {
//                     swap(intervals[i], intervals[j]);
//                 }
//             }
//         }
//     }
//     int minMeetingRooms(vector<Interval> &intervals) {
//         sort_interval(intervals);
//         vector<int> rooms;
//         if (intervals.empty()) return 0;
//         rooms.push_back(intervals[0].end);
//         for (int i = 1; i < intervals.size(); ++i)
//         {
//             int j = 0;
//             for (; j < rooms.size(); ++j)
//             {
//                 if (intervals[i].start > rooms[j])
//                 {
//                     rooms[j] = intervals[i].end;
//                     sort(rooms.rbegin(), rooms.rend());
//                     break;
//                 }
//             }
//             if (j == rooms.size()) rooms.push_back(intervals[i].end);
//         }
//         return rooms.size();
//     }
// };


// 法2：堆，每次替换最小的那个end
bool cmp (const Interval& a, const Interval& b) {
    return a.start < b.start || (a.start == b.start && a.end < b.end);
}
class Solution {
public:
    /**
     * @param intervals: an array of meeting time intervals
     * @return: the minimum number of conference rooms required
     */
    // bool static cmp(const Interval &a, const Interval &b) {
    //     // 注意：比较函数必须写在类外部（全局区域）或声明为静态函数
    //      return a.start < b.start || (a.start == b.start && a.end < b.end);
    // }
    int minMeetingRooms(vector<Interval> &intervals) {
        if (intervals.empty()) return 0;
        priority_queue<int, vector<int>, greater<int>> q; //存放end。最小堆，默认最大堆
        // sort(intervals.begin(), intervals.end());
        sort(intervals.begin(), intervals.end(), cmp);
        // q.push(intervals[0]);
        q.push(intervals[0].end);
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i].start >= q.top()) {
                q.pop(); // 用新的end替换旧的
            }
            q.push(intervals[i].end);
        }
        return q.size();
    }
};

// 法3：通用做法
// 前缀和 O(Time) Time表示最大时间
// 区间开头+1，区间结尾-1，计算前缀和数组，求最大值。
// 如果和前一个区间无重合，等不到加1就到了前一个区间尾，就减1了。遇到一个尾就会减1。
class Solution {
public:
    int minMeetingRooms(vector<Interval> &intervals) {
        map<int, int> record;
        for (auto i: intervals)
        {
            record[i.start]++;
            record[i.end]--;
        }
        int max_val = 0;
        int sum = 0;
        for (auto i: record)
        {
            sum += i.second;
            max_val = max(max_val, sum);
        }
        return max_val;
    }
};


// 法4：标准扫描线
// 扫描线 O(NlogN) N是会议数量
/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */
class Event {
public:
    int time;
    int flag;
    Event(int time, int flag) {
        this->time = time;
        this->flag = flag;
    }

    bool operator < (const Event& e) const {
        return this->time < e.time || (this->time == e.time && this->flag < e.flag); //先结束后开始.别忘了第二个条件！！！ 
    }
};

class Solution {
public:
    /**
     * @param intervals: an array of meeting time intervals
     * @return: the minimum number of conference rooms required
     */
    int minMeetingRooms(vector<Interval> &intervals) {
        vector<Event> events;
        for (auto& i: intervals) {
            events.push_back(Event(i.start, 1));
            events.push_back(Event(i.end, -1));
        }
        sort(events.begin(), events.end());
        int res = 0;
        int tmp = 0;
        for (auto& e: events) {
            tmp += e.flag;
            res = max(res, tmp);
        }
        return res;
    }
};